C/C++ - [Strutture Dati] Grafi rappresentati attraverso liste di adiacenza (sequenziali) e multiliste?

Forum - C/C++ - [Strutture Dati] Grafi rappresentati attraverso liste di adiacenza (sequenziali) e multiliste?

kommsoft (Normal User)
Newbie

Messaggi: 2
Iscritto: 17/07/2009

Postato alle 12:55
Venerdì, 17/07/2009

Salve sono nuovo!! Un saluto a tutti e complimenti x il blog!!! nel corso dello studio mi sono imbattuto in delle rappresentazioni di grafi attraverso strutture dati un po particolari:

Riesco a comprendere e rappresentare senza difficolta attraverso matrici di adiacenza e liste adiacenza concatenate i grafi. Ma non riesco a comprendere le regole per generare le rappresentazioni attraverso liste di adiacenza sequenziali e Multigrafi pur avendo la soluzione agli esercizi :

Esempio: Un grafo che ha come liste di adiacenza concatenate
a-> b->d->->(NULL)
b->a->c->(NULL)
c->d->b->e->(NULL)
d->a->c->e->(NULL)
e->d->c->(NULL)
f->(NULL)

le liste di adiacenza sequenziali sono rappresentate in un vettore di n+2l+1=19 nodi (dove n=nodi; l=lati )
a[0]=7
a[1]=9
a[2]=11
a[3]=14
a[4]=17
a[5]=19
a[6]=19
a[7]=1
a[8]=3
a[9]=0
a[10]=2
a[11]=1
a[12]=3
a[13]=4
a[14]=0
a[15]=2
a[16]=4
a[17]=2
a[18]=3

Come faccio a calcolarmi questo vettore?
/////////////
Stessa cosa per i multigrafi con lo stesso esempio:
Rappresentati arraverso la struttura [marcato,vertice1,vertice2,percorso1,per…
dove N(i) per i che va da 1 a l(numero lati) rappresenta il collegamento tra 2 nodi.

vertice0=N1->N3
vertice1=N1->N2
vertice2=N2->N4->N6
vertice3=N3->N4->N5
vertice4=N5->N6
vertice5=NULL

le multiliste sono
#0 1 n3 n2
#1 2 NULL n4
#0 3 NULL n4
#2 3 n6 n5
#3 4 NULL n6
#2 4 NULL NULL

Grazie x l'attenzione..
spero possiate darmi una mano

)

TheKaneB (Member)
Guru^2

Messaggi: 1792
Iscritto: 26/06/2009

Postato alle 16:08
Sabato, 18/07/2009

Ciao,

ho dato un'occhiata al tuo esercizio. L'algoritmo è molto semplice ma in questo momento vado di fretta e non ho il tempo di scriverlo.

Resta comunque nei paraggi, se domani trovo un po' di tempo ti faccio vedere come ottenere il vettore con un algoritmo iterativo piccolissimo, saranno a occhio e croce meno di 10 linee di codice.

Ciao, a presto ;-)

kommsoft (Normal User)
Newbie

Messaggi: 2
Iscritto: 17/07/2009

Postato alle 11:38
Martedì, 21/07/2009

Risolto

) grazie lo stesso !!!

TheKaneB (Member)
Guru^2

Messaggi: 1792
Iscritto: 26/06/2009

Postato alle 16:26
Martedì, 21/07/2009

uh, ok :-)

scusa il ritardo ma in questo periodo ho poco tempo libero... eheh ^_^

dani_adp (Normal User)
Newbie

Messaggi: 1
Iscritto: 30/08/2009

Postato alle 9:11
Domenica, 30/08/2009

Testo quotato

Postato originariamente da kommsoft:

Risolto

) grazie lo stesso !!!

io invece non riesco proprio a capire come riempire il vettore.Qualcuno mi può dare una mano?? :-|

Grazie!